package com.haidechizi.leetcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;

public class _347_前K个高频元素 {

    public List<Integer> topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        // 统计每个出现的频率
        for (int num : nums) {
            int count = map.getOrDefault(num, 0);
            map.put(num, count++);
        }

        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>((v1, v2) -> {
            return map.get(v1) - map.get(v2);
        });
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if (priorityQueue.size() < k) {
                priorityQueue.offer(entry.getKey());
            } else if (map.get(priorityQueue.peek()) < entry.getValue()) {
                priorityQueue.poll();
                priorityQueue.add(entry.getKey());
            }
        }

        List<Integer> list = new ArrayList<>();
        list.addAll(priorityQueue);
        return list;
    }
}
